/* Copyright © 2010 Brandon L Black
 *
 * This file is part of vscf.
 *
 * vscf is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * vscf is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with vscf.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Author: Brandon L Black <blblack@gmail.com>
 */

#define _IN_VSCF_C
#include "vscf.h"

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

/*
 * The initial size of the read() buffer.  Note that
 *  we can only parse a key or simple value by having
 *  it fit completely inside one buffer.  Therefore to
 *  avoid arbitrary restrictions, the read() buffer is
 *  resized by doubling if we run into a key or string
 *  value that exceeds the buffer size.
 */
#define INIT_BUF_SIZE 8192

// Default memory management
static vscf_calloc_cb_t xcalloc = calloc;
static vscf_realloc_cb_t xrealloc = realloc;
static vscf_free_cb_t xfree = free;

static void* xmalloc(size_t size) { return xrealloc(NULL, size); }

// Default error handling
static void default_err(const char* fmt, ...) {
    va_list ap;
    va_start(ap, fmt);
    vfprintf(stderr, fmt, ap);
    va_end(ap);
}
static vscf_err_cb_t err = default_err;

#define parse_error(_fmt, ...) do {\
    scnr->perr = true;\
    err("Parse error at %s line %u: " _fmt, scnr->fn, scnr->lcount, ## __VA_ARGS__);\
} while(0)

#define parse_error_noargs(_fmt) do {\
    scnr->perr = true;\
    err("Parse error at %s line %u: " _fmt, scnr->fn, scnr->lcount);\
} while(0)

/*************************************/
/*** Private data type definitions ***/
/*************************************/

typedef struct _vscf_hentry_t vscf_hentry_t;

struct _vscf_hentry_t {
    bool            marked;
    unsigned        klen;
    char*           key;
    vscf_data_t*    val;
    vscf_hentry_t*  next;
};

typedef struct {
    vscf_data_t* parent;
    vscf_type_t  type;
    unsigned     vlen;
    char*        val;
} vscf_simple_t;

typedef struct {
    vscf_data_t*  parent;
    vscf_type_t   type;
    unsigned      len;
    vscf_data_t** vals;
} vscf_array_t;

typedef struct {
    vscf_data_t*    parent;
    vscf_type_t     type;
    unsigned        child_count;
    vscf_hentry_t** children;
    vscf_hentry_t** ordered;
} vscf_hash_t;

union _vscf_data_t {
    struct {
        vscf_data_t*    parent;
        vscf_type_t     type;
    } v;
    vscf_simple_t   simple;
    vscf_array_t    array;
    vscf_hash_t     hash;
};

typedef struct {
    bool          perr;
    int           cstack_top;
    int           cs;
    int           top;
    unsigned      cstack_alloc;
    unsigned      cs_stack_alloc;
    unsigned      lcount;
    unsigned      cur_klen;
    vscf_data_t** cstack;
    int*          cs_stack;
    const char*   p;
    const char*   pe;
    const char*   eof;
    vscf_hash_t*  root;
    vscf_data_t*  cur_container;
    char*         cur_key;
    const char*   fn;
    const char*   tstart;
} vscf_scnr_t;

/*************************/
/*** Private functions ***/
/*************************/

static unsigned count2mask(unsigned x) {
    if(!x) return 1;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x;
}

static unsigned djb_hash(const char* k, unsigned klen, const unsigned hash_mask) {
   unsigned hash = 5381;

   while(klen--)
       hash = ((hash << 5) + hash) ^ *k++;

   return hash & hash_mask;
}

static vscf_hash_t* hash_new(vscf_data_t* parent) {
    vscf_hash_t* h = xcalloc(1, sizeof(vscf_hash_t));
    h->type = VSCF_HASH_T;
    h->parent = parent;
    return h;
}

static void hash_grow(vscf_hash_t* h) {
    const unsigned old_hash_mask = count2mask(h->child_count);
    const unsigned new_hash_mask = (old_hash_mask << 1) | 1;
    vscf_hentry_t** new_table = xcalloc(new_hash_mask + 1, sizeof(vscf_hentry_t*));
    for(unsigned i = 0; i <= old_hash_mask; i++) {
        vscf_hentry_t* entry = h->children[i];
        while(entry) {
            const unsigned child_hash = djb_hash(entry->key, entry->klen, new_hash_mask);
            vscf_hentry_t* slot = new_table[child_hash];
            vscf_hentry_t* next_entry = entry->next;
            entry->next = NULL;

            if(slot) {
                while(slot->next)
                    slot = slot->next;
                slot->next = entry;
            }
            else {
                new_table[child_hash] = entry;
            }

            entry = next_entry;
        }
    }

    xfree(h->children);

    h->children = new_table;
    h->ordered = xrealloc(h->ordered, (new_hash_mask + 1) * sizeof(vscf_hentry_t*));
}

static bool hash_add_val(vscf_scnr_t* scnr, vscf_hash_t* h, vscf_data_t* v) {
    if(!h->children) {
        h->children = xcalloc(2, sizeof(vscf_hentry_t*));
        h->ordered = xmalloc(2 * sizeof(vscf_hentry_t*));
    }

    const unsigned child_mask = count2mask(h->child_count);
    const unsigned child_hash = djb_hash(scnr->cur_key, scnr->cur_klen, child_mask);

    vscf_hentry_t** store_at = &(h->children[child_hash]);
    while(*store_at) {
        if((scnr->cur_klen == (*store_at)->klen)
            && !memcmp(scnr->cur_key, (*store_at)->key, scnr->cur_klen)) {
            parse_error_noargs("Duplicate hash key\n");
            return false;
        }
        store_at = &((*store_at)->next);
    }

    vscf_hentry_t* new_hentry = *store_at = xcalloc(1, sizeof(vscf_hentry_t));
    new_hentry->klen = scnr->cur_klen;
    new_hentry->key = scnr->cur_key;
    new_hentry->val = v;
    scnr->cur_key = NULL;
    scnr->cur_klen = 0;

    if(h->child_count == child_mask)
        hash_grow(h);

    h->ordered[h->child_count++] = new_hentry;

    return true;
}

static vscf_array_t* array_new(vscf_data_t* parent) {
    vscf_array_t* a = xcalloc(1, sizeof(vscf_array_t));
    a->type   = VSCF_ARRAY_T;
    a->parent = parent;
    return a;
}

static void array_add_val(vscf_array_t* a, vscf_data_t* v) {
    unsigned idx = a->len++;
    a->vals = xrealloc(a->vals, a->len * sizeof(vscf_data_t*));
    a->vals[idx] = v;
}

static vscf_simple_t* simple_new(char* val, unsigned vlen, vscf_data_t* parent) {
    vscf_simple_t* s = xcalloc(1, sizeof(vscf_simple_t));
    s->type   = VSCF_SIMPLE_T;
    s->vlen   = vlen;
    s->val    = val;
    s->parent = parent;
    return s;
}

/*
 * Takes a pointer to a constant simple key/value with len
 * Allocates necessary storage and stores the unescaped version
 *  in *out, returning the new length, which will be <= the original length
 * Note also that the returned storage is one byte longer than indicated and
 *  terminated with a NUL in that extra byte.  It serves two purposes:
 * (1) Ensuring that the data pointer of a zero-length string/key is not NULL
 *   (it points to one byte of NUL)
 * (2) Allowing the treatment of vscf strings as NUL-terminated in cases where
 *   embedded NULs are irrelevant (such as our own numeric conversions, and
 *   probably many user-code cases too).
 */
static signed unescape(vscf_scnr_t* scnr, char** outp, const char* in, unsigned len) {
    char* out = xmalloc(len + 1);
    char* out_start = out;
    for(unsigned i = 0; i < len; i++) {
        if(in[i] != '\\') {
            *out++ = in[i];
        }
        else {
            i++;
            if(in[i] <= '9' && in[i] >= '0') {
                unsigned x = ((in[i++] - '0') * 100);
                x += ((in[i++] - '0') * 10);
                x += (in[i] - '0');
                if(x > 255) {
                    parse_error("Illegal escape sequence (%u not in range 0-255)\n", x);
                    xfree(out_start);
                    return -1;
                }
                *out++ = (unsigned char)x;
            }
            else {
                *out++ = in[i];
            }
        }
    }

    unsigned final_len = out - out_start;
    out_start = xrealloc(out_start, final_len + 1); // downsize
    out_start[final_len] = 0;
    *outp = out_start;
    return final_len;
}

static bool set_key(vscf_scnr_t* scnr, const char* end) {
    unsigned rlen = end - scnr->tstart;
    signed len = unescape(scnr, &scnr->cur_key, scnr->tstart, rlen);
    if(len < 0)
        return false;
    scnr->tstart = NULL;
    scnr->cur_klen = (unsigned)len;
    return true;
}

static bool add_to_cur_container(vscf_scnr_t* scnr, vscf_data_t* v) {
    if(scnr->cur_container->v.type == VSCF_HASH_T) {
        vscf_hash_t* h = (vscf_hash_t*)scnr->cur_container;
        return hash_add_val(scnr, h, v);
    }
    else {
        vscf_array_t* a = (vscf_array_t*)scnr->cur_container;
        array_add_val(a, v);
        return true;
    }
}

static bool set_simple(vscf_scnr_t* scnr, const char* end, vscf_data_t* parent) {
    unsigned rlen = end - scnr->tstart;
    char* val;
    signed len = unescape(scnr, &val, scnr->tstart, rlen);
    if(len < 0)
        return false;
    scnr->tstart = NULL;
    vscf_simple_t* s = simple_new(val, (unsigned)len, parent);
    return add_to_cur_container(scnr, (vscf_data_t*)s);
}

static bool cstack_push(vscf_scnr_t* scnr, vscf_data_t* c) {
    if(++scnr->cstack_top == (signed)scnr->cstack_alloc)
        scnr->cstack = xrealloc(scnr->cstack, ++scnr->cstack_alloc * sizeof(vscf_data_t*));
    if(!add_to_cur_container(scnr, c))
        return false;
    scnr->cstack[scnr->cstack_top] = scnr->cur_container;
    scnr->cur_container = c;
    return true;
}

static void cstack_pop(vscf_scnr_t* scnr) {
    scnr->cur_container = scnr->cstack[scnr->cstack_top--];
}

/*** Destructors ***/

static void simple_destroy(vscf_simple_t* s) {
    xfree(s->val);
    xfree(s);
}

static void array_destroy(vscf_array_t* a);
static void hash_destroy(vscf_hash_t* h);

static void val_destroy(vscf_data_t* d) {
    switch(d->v.type) {
        case VSCF_HASH_T:   hash_destroy((vscf_hash_t*)d); break;
        case VSCF_ARRAY_T:  array_destroy((vscf_array_t*)d); break;
        case VSCF_SIMPLE_T: simple_destroy((vscf_simple_t*)d); break;
    }
}

static void array_destroy(vscf_array_t* a) {
    for(unsigned i = 0; i < a->len; i++)
        val_destroy(a->vals[i]);
    xfree(a->vals);
    xfree(a);
}

static void hash_destroy(vscf_hash_t* h) {
    for(unsigned i = 0; i < h->child_count; i++) {
        vscf_hentry_t* hentry = h->ordered[i];
        val_destroy(hentry->val);
        xfree(hentry->key);
        xfree(hentry);
    }
    xfree(h->children);
    xfree(h->ordered);
    xfree(h);
}

/************************************/
/*** The Ragel machine definition ***/
/************************************/

%%{
    machine vscf;

    action token_start  {
        scnr->tstart = fpc;
    }
    action set_key      {
        if(!set_key(scnr, fpc))
            fbreak;
    }
    action set_key_q    {
        scnr->tstart++;
        if(!set_key(scnr, fpc - 1))
            fbreak;
    }
    action set_simple   {
        if(!set_simple(scnr, fpc, scnr->cur_container))
            fbreak;
    }
    action set_simple_q {
        scnr->tstart++;
        if(!set_simple(scnr, fpc - 1, scnr->cur_container))
            fbreak;
    }
    action open_array   {
        if(!cstack_push(scnr, (vscf_data_t*)array_new(scnr->cur_container)))
            fbreak;
        fcall array;
    }
    action open_hash    {
        if(!cstack_push(scnr, (vscf_data_t*)hash_new(scnr->cur_container)))
            fbreak;
        fcall hash;
    }
    action close_array  {
        cstack_pop(scnr);
        fret;
    }
    action close_hash   {
        cstack_pop(scnr);
        fret;
    }

    # newlines, count them
    nl      = '\n' ${scnr->lcount++;};

    # Single line comment, e.g. ; dns comment or # sh comment
    slc     = ([;#] [^\n]* nl);

    # Whitespace, which includes newlines, commas, and comments
    ws      = ([ \t,] | nl | slc)+;

    # Escape sequences in general for any character-string
    escapes = ('\\' [^0-9\n]) | ('\\' digit{3}) | ('\\' nl);

    # The base set of literal characters allowed in unquoted character strings 
    chr     = [^}{;# \t\n,"=:\\] - (']'|'[');

    # An unquoted character string
    cstring = (chr | escapes)+ $1 %0;

    # Quoted character string
    qstring = '"' ([^"\n\\]|escapes|nl)* '"';

    # A simple value
    simple  = (cstring %set_simple | qstring %set_simple_q) >token_start;

    # Keys and Values
    key     = (cstring %set_key | qstring %set_key_q) >token_start;
    value = (
          simple
        | '[' $open_array
        | '{' $open_hash
    );

    # Top-level language structure
    assign  = (key ws* [=:] ws* value);
    assigns = (ws|assign)*;
    array  := (ws|value)* ']' $close_array;
    hash   := assigns '}' $close_hash;
    main   := assigns;

    write data nofinal;
}%%

static void invoke_ragel(vscf_scnr_t* scnr) {
    %%{
        prepush {
            if(scnr->top == (signed)scnr->cs_stack_alloc)
                scnr->cs_stack
                    = xrealloc(scnr->cs_stack,
                        ++scnr->cs_stack_alloc * sizeof(int));
        }
        variable stack scnr->cs_stack;
        variable top   scnr->top;
        variable cs    scnr->cs;
        variable p     scnr->p;
        variable pe    scnr->pe;
        variable eof   scnr->eof;
        write exec;
    }%%
}

/****************************/
/*** Public API functions ***/
/****************************/

void vscf_set_err_cb(vscf_err_cb_t e) { err = e; }
void vscf_set_calloc_cb(vscf_calloc_cb_t c) { xcalloc = c; }
void vscf_set_realloc_cb(vscf_realloc_cb_t r) { xrealloc = r; } 
void vscf_set_free_cb(vscf_free_cb_t f) { xfree = f; }

const vscf_data_t* vscf_scan_fd(int fd, const char* fn) {
    vscf_scnr_t* scnr = xcalloc(1, sizeof(vscf_scnr_t));
    unsigned buf_size = INIT_BUF_SIZE;
    char* buf = xmalloc(buf_size);
    char* read_at;
    unsigned have;
    int len, space;

    scnr->lcount = 1;
    scnr->fn = fn ? fn : "";
    scnr->root = hash_new(NULL);
    scnr->cur_container = (vscf_data_t*)scnr->root;
    scnr->cstack_top = -1;
    scnr->cs = vscf_start;

    while(!scnr->eof) {
        if(scnr->tstart == NULL)
            have = 0;
        else {
            have = scnr->pe - scnr->tstart;
            if(scnr->tstart == buf) {
                buf_size *= 2;
                buf = xrealloc(buf, buf_size);
            }
            else {
                memmove(buf, scnr->tstart, have);
            }
            scnr->tstart = buf;
        }

        space = buf_size - have;
        scnr->p = read_at = buf + have;

        len = read(fd, read_at, space);
        if(len < 0) {
            err("read() of '%s' failed: errno %i\n", scnr->fn, errno);
            return NULL;
        }

        scnr->pe = scnr->p + len;

        if(len < space)
            scnr->eof = scnr->pe;

        invoke_ragel(scnr);

        if(scnr->cs == vscf_error)
            parse_error_noargs("syntax error\n");
        if(scnr->perr)
            return NULL;
    }

    if(scnr->cstack) xfree(scnr->cstack);
    if(scnr->cs_stack) xfree(scnr->cs_stack);
    xfree(buf);

    const vscf_data_t* retval = (const vscf_data_t*) scnr->root;
    xfree(scnr);
    return retval;
}

const vscf_data_t* vscf_scan_string(const char* s, unsigned len, const char* fn) {
    if(!s || !len) return NULL;

    vscf_scnr_t* scnr = xcalloc(1, sizeof(vscf_scnr_t));
    scnr->lcount = 1;
    scnr->fn = fn ? fn : "";
    scnr->root = hash_new(NULL);
    scnr->cur_container = (vscf_data_t*)scnr->root;
    scnr->cstack_top = -1;
    scnr->cs = vscf_start;

    scnr->p = s;
    scnr->pe = scnr->eof = s + len;
    invoke_ragel(scnr);
    if(scnr->cs == vscf_error)
        parse_error_noargs("syntax error\n");
    if(scnr->perr)
        return NULL;

    if(scnr->cstack) xfree(scnr->cstack);
    if(scnr->cs_stack) xfree(scnr->cs_stack);

    const vscf_data_t* retval = (const vscf_data_t*) scnr->root;
    xfree(scnr);
    return retval;
}

const vscf_data_t* vscf_scan_filename(const char* fn) {
    int fd = open(fn, O_RDONLY);
    if(fd < 0) {
        err("Cannot open config file '%s' for reading: errno %i\n", fn, errno);
        return NULL;
    }

    const vscf_data_t* retval = vscf_scan_fd(fd, fn);
    if(close(fd)) {
        err("Cannot close config file '%s': errno %i\n", fn, errno);
        return NULL;
    }
    return retval;
}

void vscf_destroy(vscf_data_t* d) { hash_destroy((vscf_hash_t*)d); }

vscf_type_t vscf_get_type(const vscf_data_t* d) {
    return d->v.type;
}

const vscf_data_t* vscf_get_parent(const vscf_data_t* d) {
    return d->v.parent;
}

unsigned vscf_simple_get_len(const vscf_data_t* d) {
    return ((const vscf_simple_t*)d)->vlen;
}

const char* vscf_simple_get_data(const vscf_data_t* d) {
    return ((const vscf_simple_t*)d)->val;
}

unsigned vscf_array_get_len(const vscf_data_t* d) {
    return ((const vscf_array_t*)d)->len;
}

const vscf_data_t* vscf_array_get_item(const vscf_data_t* d, unsigned idx) {
    const vscf_array_t* a = (const vscf_array_t*)d;
    if(idx >= a->len) return NULL;
    return a->vals[idx];
}

unsigned vscf_hash_get_nkeys(const vscf_data_t* d) {
    return ((const vscf_hash_t*)d)->child_count;
}

const vscf_data_t* vscf_hash_get_item(const vscf_data_t* d, const char* key, unsigned klen, bool set_mark) {
    const vscf_hash_t* h = (const vscf_hash_t*)d;
    if(h->child_count) {
        unsigned child_mask = count2mask(h->child_count);
        unsigned child_hash = djb_hash(key, klen, child_mask);
        vscf_hentry_t* he = h->children[child_hash];
        while(he) {
            if((klen == he->klen) && !memcmp(key, he->key, klen)) {
                if(set_mark) he->marked = true;
                return he->val;
            }
            he = he->next;
        }
    }

    return NULL;
}

void vscf_hash_iterate(const vscf_data_t* d, bool ignore_mark, vscf_hash_iter_cb_t f, void* data) {
    const vscf_hash_t* h = (const vscf_hash_t*)d;
    for(unsigned i = 0; i < h->child_count; i++) {
        const vscf_hentry_t* hentry = h->ordered[i];
        if(!ignore_mark || !hentry->marked)
            if(!f(hentry->key, hentry->klen, hentry->val, data))
                return;
    }
}

bool vscf_simple_get_as_ulong(const vscf_data_t* d, unsigned long* out) {
    vscf_simple_t* s = (vscf_simple_t*)d;

    if(!s->vlen) return false;
    for(unsigned i = 0; i < s->vlen; i++) {
        if(s->val[i] < '0' || s->val[i] > '9')
            return false;
    }

    char* eptr;
    char* real_eptr = s->val + s->vlen;
    errno = 0;
    unsigned long retval = strtoul(s->val, &eptr, 10);
    if(errno || eptr != real_eptr) {
        errno = 0;
        return false;
    }

    *out = retval;
    return true;
}

bool vscf_simple_get_as_long(const vscf_data_t* d, long* out) {
    vscf_simple_t* s = (vscf_simple_t*)d;

    if(!s->vlen) return false;
    char* eptr;
    char* real_eptr = s->val + s->vlen;
    errno = 0;
    long retval = strtol(s->val, &eptr, 10);
    if(errno || eptr != real_eptr) {
        errno = 0;
        return false;
    }

    *out = retval;
    return true;
}

bool vscf_simple_get_as_double(const vscf_data_t* d, double* out) {
    vscf_simple_t* s = (vscf_simple_t*)d;

    if(!s->vlen) return false;
    char* eptr;
    char* real_eptr = s->val + s->vlen;
    errno = 0;
    double retval = strtod(s->val, &eptr);
    if(errno || eptr != real_eptr) {
        errno = 0;
        return false;
    }

    *out = retval;
    return true;
}

bool vscf_simple_get_as_bool(const vscf_data_t* d, bool* out) {
    vscf_simple_t* s = (vscf_simple_t*)d;

    if(s->vlen == 4
        && (s->val[0] == 'T' || s->val[0] == 't')
        && (s->val[1] == 'R' || s->val[1] == 'r')
        && (s->val[2] == 'U' || s->val[2] == 'u')
        && (s->val[3] == 'E' || s->val[3] == 'e')) {
        *out = true;
        return true;
    }

    if(s->vlen == 5
        && (s->val[0] == 'F' || s->val[0] == 'f')
        && (s->val[1] == 'A' || s->val[1] == 'a')
        && (s->val[2] == 'L' || s->val[2] == 'l')
        && (s->val[3] == 'S' || s->val[3] == 's')
        && (s->val[4] == 'E' || s->val[4] == 'e')) {
        *out = false;
        return true;
    }

    return false;
}

